/***************************************************************************************************
  *Copyright(C),2010-2016,Sumscope
  *FileName	:  pinyin_search_idvec.cpp
  *Author	:  scofined.qi
  *Version	:  1.0
  *Date		:  2017/06/04
  *Desc		:  //用于主要说明此程序文件完成的主要功能
  *Relation :  
  *Others	:  //其他内容说明
  *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
  *History	:  //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
***************************************************************************************************/
#include "pinyin_search_idvec.h"
#include "pinyin_search_idstore.h"
#include "pinyin_search_set.h"

#ifndef BASSERTS
#define BASSERTS //
#endif
#ifndef BASSERT
#define BASSERT //
#endif

namespace qb{
	namespace base{
		using namespace spell;
#define FIND_AFTER(RET,KEY,POS) {int temp=find_fast(KEY,POS);RET=temp>=0?temp:find_slow2(KEY,POS);}
//#define FIND_AFTER(RET,KEY,POS) RET = find_after_old(KEY,POS)

		namespace internal{
			IndexIdVec::IndexIdVec() :m_first(0), m_count(0), m_capcity(0)
			{

			}

			IndexIdVec::IndexIdVec(IndexId* first, int count, int capcity)
			{
				bind(first, count, capcity);
			}

			void IndexIdVec::bind(IndexId* first, int count, int capcity)
			{
				m_first = first; m_count = count; m_capcity = capcity;
			}

			void IndexIdVec::copyfrom(const IndexIdVec& iivec)
			{
				memcpy(m_first, iivec.m_first, sizeof(IndexId)*m_count);
			}

			void IndexIdVec::copyfrom(const InverseSet& iset)
			{
				//BASSERT(m_first && m_capcity >= iset.size());
				m_count = 0;
				for (InverseSet::const_iterator it = iset.cbegin(); it != iset.cend(); ++it)
				{
					m_first[m_count++] = makeid(it->first, it->second);
				}
			}

			void IndexIdVec::copyto(InverseSet& iset)
			{
				iset.reset();
				for (int i = 0; i < m_count; i++)
					iset.add(getkey(m_first[i]));
			}
			bool IndexIdVec::equal(const InverseSet& iset)const
			{
				if (m_count != iset.size())
					return false;
				if (m_count > 0 && m_first == NULL)
					return false;
				int i = 0;
				for (InverseSet::const_iterator it = iset.cbegin(); i<m_count && it != iset.cend(); ++it,++i)
				{
					IndexId id = makeid(it->first, it->second);
					if (id != m_first[i])
						return false;
				}
				return true;
			}
			IndexIdVec::~IndexIdVec()
			{
			}

			bool IndexIdVec::add(int key)
			{
				//BASSERT(m_first && m_capcity > 0);
				int ipos = 0;
				FIND_AFTER(ipos, key, 0);
				//BASSERT(ipos >= 0 && ipos <= m_count);
				IndexId* pid = m_first + ipos;
				if (ipos >= 0 && ipos < m_count)
				{
					if (getkey(*pid) == key)
					{
						*pid = makeid(key, getval(*pid) + 1);
						return true;
					}
				}

				// 将ipos后面的往后移动一个位置
				if (m_count >= m_capcity)
					return false;

				if (m_count>ipos)
					memmove(m_first + ipos + 1, m_first + ipos, (m_count - ipos)*sizeof(IndexId));
				*pid = makeid(key, 1);
				m_count++;
				return true;
			}

			void IndexIdVec::remove(int key)
			{
				int ipos = 0;
				FIND_AFTER(ipos, key, 0);
				if (ipos >= 0 && ipos < m_count)
				{
					IndexId* pid = m_first + ipos;
					if (getkey(*pid) != key)
						return;
					*pid = makeid(key, getval(*pid) - 1);
					if (getval(*pid) <= 0)
					{
						// 将后面的向前移动
						IndexId* dest = m_first + ipos;
						IndexId* source = m_first + ipos + 1;
						IndexId* end = m_first + m_count;
						//for (; source < end;)
						//	*dest++ = *source++;
						if (m_count>ipos+1)
							memmove(dest, source, sizeof(IndexId)*(m_count-ipos-1));
						m_count--;
					}
				}
			}
			void IndexIdVec::check()
			{
				if (m_first && m_count>0)
				{
					int nerror = 0;
					int last = getkey(*m_first);
					for (int i = 1; i < m_count;i++)
					{
						if (last >= getkey(m_first[i]))
							nerror++;
						last = getkey(m_first[i]);
					}
					BASSERTS(nerror <= 0, "nerror=%d",nerror);
				}
			}
			bool IndexIdVec::exist(int key) const
			{
				int ipos = 0; FIND_AFTER(ipos, key, 0);
				if (ipos < 0 || ipos >= m_count)	return false;
				return getkey(m_first[ipos]) == key;
			}

			void IndexIdVec::clear()
			{
				if (m_first)
					m_first[0] = 0;
				m_count = 0;
			}
			void IndexIdVec::intersect(const InverseSet& iset)
			{
				int npos = 0;
				int ncount = 0;
				if (m_count <= iset.size())
				{
					for (int i = 0; i < m_count; i++)
					{
						int key = spell::getkey(m_first[i]);
						npos = iset.find(key, npos);
						if (npos >= iset.size())
							break;
						if (iset.at(npos).getkey() == key)
							m_first[ncount++] = spell::makeid(key, iset.at(i).getval());
					}
				}
				else
				{
					for (int i = 0; i < iset.size(); i++)
					{
						int key = iset.at(i).getkey();
						npos = find_after(key, npos);
						if (npos >= m_count)
							break;
						if (key == spell::getkey(m_first[npos]))
							m_first[ncount++] = spell::makeid(key, iset.at(i).getval());
					}
				}
				if (0)
				{
					for (int i = 0; i < m_count; i++)
					{
						if (iset.exist(getkey(m_first[i])))
						{
							m_first[ncount++] = m_first[i];
						}
					}
				}
				m_count = ncount;
				if (m_count < m_capcity && m_first)
					m_first[m_count] = 0;
			}
			void IndexIdVec::intersect(const IndexIdVec& iis)
			{
				// 如果自身比iis要大,那么取小的作为待遍历的容器
				// 取大的作为搜索容器,这样做,减少查询次数,略微提升性能18%
				// 改进算法,使用find_after,单项测试提升3倍,整体提升1倍
				intersect_old(iis);
				return;
				int ncount = 0, npos = 0;
				bool larger = size() > iis.size();
				int nloop = larger ? iis.size() : size();
				int nmaxpos = larger ? size() : iis.size();
				const IndexId* first = larger ? iis.m_first : m_first;
				const IndexIdVec* search = larger ? this : &iis;
				int ki = 0;
				
				for (int i = 0; i < nloop; i++)
				{
					ki = spell::getkey(first[i]);
					//ret = (const Value*)bsearch(&ki, search->m_first, search->size(), sizeof(int), KeyCompare::CompByKey);
					
					//npos = npos; //search->find_after(ki, npos);
					//FIND_AFTER(npos, ki, npos);
					int temp = search->find_after(ki, npos);
					if (temp >= nmaxpos)
						break;
					if (getkey(search->m_first[temp]) == ki)
						m_first[ncount++] = first[i];
					npos = temp+1;
				}

				m_count = ncount;
				if (m_count < m_capcity && m_first)
					m_first[m_count] = 0;
				return;
			}
			void IndexIdVec::intersect_old(const IndexIdVec& iis)
			{
				check();
				(const_cast<IndexIdVec*>(&iis))->check();
				int ncount = 0;
				for (int i = 0; i < m_count; i++)
				{
					if (iis.exist(getkey(m_first[i])))
					{
						m_first[ncount++] = m_first[i];
					}
				}
				m_count = ncount;
				if (m_capcity > m_count)
					memset(m_first + m_count, 0, (m_capcity - m_count) * sizeof(IndexId));
			}
			void IndexIdVec::transform()
			{
				if (m_first)
				{
					for (int i = 0; i < m_count; i++)
					{
						m_first[i] = getkey(m_first[i]);
					}
				}
			}

			bool IndexIdVec::get(int index, KeyType& key, CountType& val) const
			{
				if (index >= 0 && index < m_count && m_first)
				{
					key = spell::getkey(m_first[index]);
					val = spell::getval(m_first[index]);
					return true;
				}
				key = val = 0;
				return false;
			}
			int IndexIdVec::find_slow2(int key, int npos) const
			{
				// 从npos开始查找第一个=key的位置,返回-1表示找不到
				int left = npos, right = m_count - 1, mid = 0;
				int kl, kr, km, step;
				kl = getkey(m_first[left]);
				right = left + (key - kl);
				if (right >= m_count - 1)
					right = m_count - 1;
				kr = getkey(m_first[right]);
				BASSERT(kr >= key);
				int gap = 16;//经过大量测试,16效果最佳
				int i = -1;
				while (left + gap < right)
				{
					// 二分法:step = (right - left) >> 1;
					// 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
					// 经过测试,真实11w债券数据,比例法性能是二分法的2倍
					step = 1.0*(right - left)*(key - kl) / (kr - kl);
					mid = left + (step < 1 ? gap : step);
					km = getkey(m_first[mid]);
					if (key == km){ i = mid; break; }
					if (key < km)
					{
						right = mid;
						kr = getkey(m_first[right]);
					}
					else
					{
						left = mid + 1;
						kl = getkey(m_first[left]);
					}
				}
				if (i < 0)
				{
					i = left;
					for (; i <= right; i++)
					{
						if (key <= getkey(m_first[i]))
							break;
					}
				}

				BASSERT(i < m_count && getkey(m_first[i]) >= key);
				BASSERT(i == 0 || getkey(m_first[i - 1]) < key);
				return i;
			}
			int IndexIdVec::find_slow(int key, int npos) const
			{
				//return find_after_new(key, npos);
				// 从npos开始查找第一个>=key的位置,返回-1表示找不到
				int left = npos, right = m_count - 1, mid = 0;
				int kl, kr, km, step;
				kl = getkey(m_first[left]);
				kr = getkey(m_first[right]);
				const int gap = 16;//经过大量测试,16效果最佳
				int i = -1;
				while (left + gap < right)
				{
					// 二分法:step = (right - left) >> 1;
					// 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
					// 经过测试,真实11w债券数据,比例法性能是二分法的2倍
					step = 1.0*(right - left)*(key - kl) / (kr - kl);
					mid = left + (step < 1 ? gap : step);
					km = getkey(m_first[mid]);
					if (key == km){ i = mid; break; }
					if (key < km)
					{
						right = mid;
						kr = getkey(m_first[right]);
					}
					else
					{
						left = mid + 1;
						kl = getkey(m_first[left]);
					}
				}
				if (i < 0)
				{
					i = left;
					for (; i <= right; i++)
					{
						if (key <= getkey(m_first[i]))
							break;
					}
				}

				BASSERT(i < m_count && getkey(m_first[i]) >= key);
				BASSERT(i == 0 || getkey(m_first[i - 1]) < key);
				return i;
			}
			int IndexIdVec::find_after(int key, int npos) const
			{
				//return find_after_new(key, npos);
				// 从npos开始查找第一个>=key的位置,返回-1表示找不到
				int pos = find_fast(key, npos);
				if (pos < 0)pos = find_slow(key, npos);
				return pos;
			}
			int IndexIdVec::find_after_old(int key, int npos) const
			{
				if (npos < 0 || m_first == nullptr || npos >= m_count)
					return m_count;
				if (key <= spell::getkey(m_first[npos]))
					return npos;
				if (m_count >= 1)
				{
					int last = spell::getkey(m_first[m_count - 1]);
					if (key > last)return m_count;
					//if (key == last)return m_count - 1;
				}
				int left = npos, right = m_count - 1, mid = 0;
				int kl, kr, km, step;
				kl = getkey(m_first[left]);
				kr = getkey(m_first[right]);
				int gap = 16;//经过大量测试,16效果最佳
				int i = -1;
				while (left + gap < right)
				{
					// 二分法:step = (right - left) >> 1;
					// 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
					// 经过测试,真实11w债券数据,比例法性能是二分法的2倍
					step = 1.0*(right - left)*(key - kl) / (kr - kl);
					mid = left + (step < 1 ? gap : step);
					km = getkey(m_first[mid]);
					if (key == km){ i = mid; break; }
					if (key < km)
					{
						right = mid;
						kr = getkey(m_first[right]);
					}
					else
					{
						left = mid + 1;
						kl = getkey(m_first[left]);
					}
				}
				if (i < 0)
				{
					i = left;
					for (; i <= right; i++)
					{
						if (key <= getkey(m_first[i]))
							break;
					}
				}

				BASSERT(i < m_count && getkey(m_first[i]) >= key);
				BASSERT(i == 0 || getkey(m_first[i - 1]) < key);
				return i;
			}
			int IndexIdVec::find(int key) const
			{
				//BASSERT(m_first);
				if (m_count<=0 || key <= getkey(m_first[0]))
					return 0;
				if (key > getkey(m_first[m_count - 1]))
					return m_count;

				int left = 0, right = m_count, mid = 0;
				while (left + 4 < right)
				{
					mid = (left + right) >> 1;
					if (key < getkey(m_first[mid]))
						right = mid;
					else
						left = mid;
				}

				int i = left;
				for (; i < right; i++)
				{
					if (key <= getkey(m_first[i]))
						break;
				}
				return i;
			}

		}
	}
}
